let arr = [1, 8, 6, 4, 8, 9, 6, 76, 9]
//冒泡排序 每次比较都交换值 
function sort1(arr) {
  for (i = 0; i < arr.length; i++) {
    for (j = i + 1; j < arr.length; j++) {
      if (arr[i] > arr[j]) {
        let temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
      }
    }
  }
  return arr
}
//选择排序 每次比较只交换下标 最后交换值
function sort2(arr) {
  for (i = 0; i < arr.length; i++) {
    let min = i
    for (j = i + 1; j < arr.length; j++) {
      if (arr[min] > arr[j]) {
        min=j
      }
    }
   let t=arr[i]
   arr[i]=arr[min]
   arr[min]=t
  }
  return arr
}
console.log(sort2(arr))

//直接插入排序 每次取原数组待排序的值插入到已经排好序的数组中
function sort3(arr){
  for(i=1;i<arr.length;i++){
    let j=i-1
    let key=arr[i]
    while(key<arr[j]&&j>=0){
      arr[j+1]=arr[j]
      j--
    }
    arr[j+1]=key
  }
  return arr
}
//希尔排序 插入排序的变种
function shellSort(arr) {
  let len = arr.length;
  // gap 即为增量
  for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < len; i++) {
      let j = i;
      let current = arr[i];
      while(j - gap >= 0 && current < arr[j - gap]) {
        arr[j] = arr[j - gap];
        j = j - gap;
      }
      arr[j] = current;
    }
  }
}
//快速排序 高频考点 分冶思想将大问题化成小问题 T(n) = 2*T(n/2) + a*n所以最优为Olon2n 最差即原数组已经是排好序的数组时间复杂度为O(n^2)
function sort4(arr, i, j) {
  let left = i
  let right = j
  let pivot = arr[left]
  if (arr.length <= 1) {
    return arr
  }
  if (i < j) {
    while (i < j) {
      while (pivot <= arr[j] && i < j) {
        j--
      }
      if (i < j) {
        arr[i++] = arr[j]
      }
      while (pivot >= arr[i] && i < j) {
        i++
      }
      if (i < j) {
        arr[j--] = arr[i]
      }
    }
    arr[j] = pivot
    sort4(arr, left, j - 1)
    sort4(arr, j + 1, right)
    return arr
  }
}
//归并排序
function mergeSort(arr) {
  const length = arr.length;
  if (length === 1) { //递归算法的停止条件，即为判断数组长度是否为1
      return arr;
  }
  const mid = Math.floor(length / 2);
 
  const left = arr.slice(0,  mid);
  const right = arr.slice(mid, length);

  return merge(mergeSort(left), mergeSort(right)); //要将原始数组分割直至只有一个元素时，才开始归并
}

function merge(left, right) {
  const result = [];
  let il = 0;
  let ir = 0;

  //left, right本身肯定都是从小到大排好序的
  while( il < left.length && ir < right.length) {
      if (left[il] < right[ir]) {
          result.push(left[il]);
          il++;
      } else {
          result.push(right[ir]);
          ir++;
      }
      
  }

  //不可能同时存在left和right都有剩余项的情况, 要么left要么right有剩余项, 把剩余项加进来即可
  while (il < left.length) { 
      result.push(left[il]);
      il++;
  }
  while(ir < right.length) {
      result.push(right[ir]);
      ir++;
  }
  return result;
}
//堆排序
// 交换两个节点
function swap(A, i, j) {
  let temp = A[i];
  A[i] = A[j];
  A[j] = temp; 
}

// 将 i 结点以下的堆整理为大顶堆，注意这一步实现的基础实际上是：
// 假设 结点 i 以下的子堆已经是一个大顶堆，shiftDown函数实现的
// 功能是实际上是：找到 结点 i 在包括结点 i 的堆中的正确位置。后面
// 将写一个 for 循环，从第一个非叶子结点开始，对每一个非叶子结点
// 都执行 shiftDown操作，所以就满足了结点 i 以下的子堆已经是一大
//顶堆
function shiftDown(A, i, length) {
  let temp = A[i]; // 当前父节点
// j<length 的目的是对结点 i 以下的结点全部做顺序调整
  for(let j = 2*i+1; j<length; j = 2*j+1) {
    temp = A[i];  // 将 A[i] 取出，整个过程相当于找到 A[i] 应处于的位置
    if(j+1 < length && A[j] < A[j+1]) { 
      j++;   // 找到两个孩子中较大的一个，再与父节点比较
    }
    if(temp < A[j]) {
      swap(A, i, j) // 如果父节点小于子节点:交换；否则跳出
      i = j;  // 交换后，temp 的下标变为 j
    } else {
      break;
    }
  }
}

// 堆排序
function heapSort(A) {
  // 初始化大顶堆，从第一个非叶子结点开始
  for(let i = Math.floor(A.length/2-1); i>=0; i--) {
    shiftDown(A, i, A.length);
  }
  // 排序，每一次for循环找出一个当前最大值，数组长度减一
  for(let i = Math.floor(A.length-1); i>0; i--) {
    swap(A, 0, i); // 根节点与最后一个节点交换
    shiftDown(A, 0, i); // 从根节点开始调整，并且最后一个结点已经为当
                         // 前最大值，不需要再参与比较，所以第三个参数
                         // 为 i，即比较到最后一个结点前一个即可
  }
}